Теорема Ейлера (теорія чисел)

Теорема Ейлера (Ойлера) — одне з основних тверджень елементарної теорії чисел стверджує, що

якщо $\ a$ і $\ m$ взаємно_прості, то $a^{\varphi (m)}\equiv 1{\pmod {m}}$,

де $\varphi (m)$ — функція Ейлера.

Частковим випадком теореми Ейлера при простому $\ m$ є мала теорема Ферма.

В свою чергу теорема Ейлера є частковим випадком теореми Лагранжа.

Доведення

Нехай $x_{1},...,x_{\varphi (m)}$ — всі натуральні числа, менші $m$ і взаємно прості з ним.

Розглянем всеможливі добутки $ax_{i}$ для всіх $i$ від $1$ до $\varphi (m)$.

Оскільки $a$ взаємно просте з $m$ і $x_{i}$ взаємно прості з $m$, то і $ax_{i}$ також взаємно прості з $m$, тобто $ax_{i}\equiv x_{j}{\pmod {m}}$ для деякого $j$.

Далі маємо, що всі остачі від ділення $ax_{i}$ на $m$ відмінні. Справді, нехай це не так, тобто існують такі $i_{1}\neq i_{2}$, що

$ax_{i_{1}}\equiv ax_{i_{2}}{\pmod {m}}$.

Тоді $a(x_{i_{1}}-x_{i_{2}})\equiv 0{\pmod {m}}$.

Оскільки $a$ взаємно просте з $m$, то остання рівність рівносильна тому, що

$x_{i_{1}}-x_{i_{2}}\equiv 0{\pmod {m}}$ або $x_{i_{1}}\equiv x_{i_{2}}{\pmod {m}}$.

Це неможливо, оскільки числа $x_{1},...,x_{\varphi (m)}$ попарно відмінні по модулю $m$.

Перемножимо всі рівності $ax_{i}\equiv x_{j}{\pmod {m}}$. Одержуємо:

$x_{1}...x_{\varphi (m)}a^{\varphi (m)}=x_{1}...x_{\varphi (m)}{\pmod {m}}$

або

$x_{1}...x_{\varphi (m)}(a^{\varphi (m)}-1)=0{\pmod {m}}$.

Так як число $x_{1}...x_{\varphi (m)}{\pmod {m}}$ взаємно просте з $m$, то остання рівність рівносильна тому, що

$a^{\varphi (m)}-1=0{\pmod {m}}$ або $a^{\varphi (m)}\equiv 1{\pmod {m}}$.

Застосування

За допомогою даної теореми можна легко обчислювати модуль великих степенів. Наприклад, ми хочемо обчислити 7²²² (mod 10). Маємо, що 7 і 10 є взаємно простими і φ(10) = 4. Отже, згідно з теоремою Ейлера 7⁴ ≡ 1 (mod 10) і як наслідок 7²²² ≡ 7^{4x55 + 2} ≡ (7⁴)⁵⁵x7² ≡ 1⁵⁵x7² ≡ 49 ≡ 9 (mod 10).

Теорема Ейлера є також теоретичною основою криптографічної системи RSA.

Література

Українською

• (укр.) Гаврилків В. М. Елементи теорії груп та теорії кілець. — І.-Ф.  : Голіней, 2023. — 153 с.

Іншими мовами

• Чандрасекхаран К. Введение в аналитическую теорию чисел. — Москва : Мир, 1974. — 187 с.(рос.)
• Бухштаб А. А. Теория чисел, 2-е издание, М., 1966
• Трост Э. Простые числа, пер. с нем., М., 1959